Geometry / Nearest neighbor (Bibtex)

P46: Enumeration of the $k$ smallest distances between pairs of points

Input:

$n$ points in a plane.

Output:

The $k$ smallest distances between pairs of points in non-decreasing order.

Complexity:

$O(n \log n + k \log k)$ total time and $O(n + k)$ space.

Comment:

Reference:

[Dickerson1992] (Bibtex)